package sort;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class Sort {
    public static void random(int[] arr) {
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            // 随机赋值 [0,2) 之间的值
            arr[i] = random.nextInt(10);
        }
    }

    // 插入排序
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // i下标的元素就是我们要抽的 "牌"
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                // 将这张牌从右到左依次比较
                // 如果 j下标比 这张牌大, 就应该放在后面
                if (tmp < arr[j]) {
                    // 因为"牌" 已经抽出来了, 直接让 j 下标的元素覆盖掉后面的值
                    arr[j + 1] = arr[j];
                } else {
                    // 如果不大于, 说明这张牌是较大的, 就应该待在后面, 进入下一次循环, 抽后面的牌
                    break;
                }
            }
            // 走到这, 说明这张牌走到了应该到的位置, 放置即可
            arr[j + 1] = tmp;
        }
    }

    // 希尔排序
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shell(arr, gap);
        }
    }

    private static void shell(int[] arr, int gap) {
        // 希尔排序的底层逻辑实际上还是插入排序
        for (int i = gap; i < arr.length; i += gap) {
            // 抽牌
            int tmp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (tmp < arr[j]) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + gap] = tmp;
        }
    }

    // 选择排序(时间复杂度最稳定的算法)
    public static void selectSort(int[] arr) {
        // i 下标前面的数是已排序区间,i下标及其后面则是待排序区间
        for (int i = 0; i < arr.length; i++) {
            // 假设min是最小的元素下标
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                // j下标负责去找待排序区间中最小的元素, 如果 j下标元素比 i下标元素还小, 两者交换
                if (arr[j] < arr[min]) {
                    // 如果j下标的元素比min下标的元素还要小,说明j下标此时才是最小元素的下标
                    min = j;
                }
            }
            // 找到最小元素的下标后, 交换 i 与 min 指向的元素
            swap(i, min, arr);
        }
    }

    private static void swap(int j, int i, int[] arr) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    // 堆排序
    // 第一种, 将数组构建成小根堆, 然后依次出堆顶元素
    public static void heapSort2(int[] arr) {
        int length = arr.length;
        for (int parent = (length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, length, arr);
        }

        // 调整为小根堆结构后, 依次出堆顶元素
        while (length != 0) {
            System.out.print(poll(arr, length) + "  ");
            length--;
        }
    }

    private static int poll(int[] arr, int length) {
        int size = length;
        if (size == 0) {
            throw new IndexOutOfBoundsException("堆为空, 无法删除");
        }
        int result = arr[0];
        swap(0, size - 1, arr);
        // 从0下标开始向下调整
        shiftDown(0, size - 1, arr);
        return result;
    }

//    private static void shiftDown(int parent, int length, int[] arr) {
//        // 通过父节点parent下标拿到左孩子节点
//        int child = 2 * parent + 1;
//        while (child < length) {
//            // 根据二叉树的第五性质, 孩子节点要小于总结点个数, 才说明有这个孩子节点, 才能进入循环
//            // 进行向下调整
//            if (child + 1 < length && arr[child] > arr[child + 1]) {
//                // child+1 < length 说明存在右孩子节点
//                // 构建小根堆, child 需要指向两个孩子节点中最小的那个
//                child = child + 1;
//            }
//            // 向下调整
//            if (arr[child] < arr[parent]) {
//                // 如果孩子节点值小于父节点, 要交换之后才能是小根堆结构
//                swap(child, parent, arr);
//                // 交换之后, 子节点变为父节点, 继续向下调整
//                parent = child;
//                child = 2 * parent + 1;
//            }else {
//                break;
//            }
//        }
//    }

    // 第二种堆的排序, 构建大根堆, 然后类似于删除堆顶元素, 将最大的值放到最后面, 然后对堆顶元素进行向下调整
    public static void heapSort(int[] arr) {
        // 构建大根堆
        creatHeap(arr);

        // 按照删除逻辑, 把堆顶元素放到最后
        sortHeap(arr);
    }

    private static void sortHeap(int[] arr) {
        int size = arr.length;
        while (size != 0) {
            swap(0, size - 1, arr);
            size--;
            shiftDown(0, size, arr);
        }
    }

    // 构建大根堆
    private static void creatHeap(int[] arr) {
        int length = arr.length;
        // length-1 拿到最后一个叶节点 再-1 就是二叉树的性质五
        for (int parent = (length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, length, arr);
        }
    }

    // 向下调整
    private static void shiftDown(int parent, int length, int[] arr) {
        // 拿到左孩子节点
        int child = 2 * parent + 1;
        while (child < length) {
            // child下标小于length才说明存在孩子节点
            if (child + 1 < length && arr[child] < arr[child + 1]) {
                // 如果右孩子节点大于左孩子, child 指向较大者
                child = child + 1;
            }

            // 向下调整
            if (arr[child] > arr[parent]) {
                swap(child, parent, arr);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] arr) {
        boolean flag = false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j + 1] < arr[j]) {
                    swap(j + 1, j, arr);
                    flag = true;
                }
            }
            if (!flag) {
                // 如果flag为false, 说明本轮次并没有发生数据交换, 说明该数组全体有序了
                // 不需要再去遍历了
                break;
            }
        }
    }

    // 快速排序
    public static void quickSort(int[] arr) {
        // 0 表示当前数组的最左区间元素
        // arr.length 表示当前数组的最右区间元素
        hoareQuick(arr, 0, arr.length - 1);
    }

    private static void hoareQuick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 选取基准值
        int pivot = partition(arr, left, right);
        hoareQuick(arr, left, pivot - 1);
        hoareQuick(arr, pivot + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int pivotIndex = left;
        while (left < right) {
            // 右边先寻找比基准值小的
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            // 然后才是左边开始找
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            swap(left, right, arr);
        }
        swap(left, pivotIndex, arr);
        return left;
    }

    // 优化快排
    // 取 "中位数"
    private static int getMid(int[] arr, int left, int right) {
        // 拿到中间值
        int mid = left + ((right - left) >> 1);
        if (arr[left] > arr[right]) {
            if (arr[mid] < arr[right]) {
                return right;
            } else if (arr[mid] > arr[left]) {
                return left;
            } else {
                return mid;
            }
        } else {
            // arr[left] < arr[right]
            if (arr[mid] < arr[left]) {
                return left;
            } else if (arr[mid] > arr[right]) {
                return right;
            } else {
                return mid;
            }
        }
    }

    // 前后挖坑法
    private static void holeQuick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 当子区间容量小于一定范围后, 直接使用插入排序
        if (right - left + 1 < 20) {
            insertSort(arr);
            return;
        }
        int pivotIndex = getMid(arr, left, right);
        // 将拿到的 "中位数" , 作为基准值
        swap(left, pivotIndex, arr);
        int pivot = partition(arr, left, right);
        hoareQuick(arr, left, pivot - 1);
        hoareQuick(arr, pivot + 1, right);
    }

    private static int holePartition(int[] arr, int left, int right) {
        // 选择基准值, 并拿出来形成一个 "坑"
        int pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            // 在右区间找到比基准值小的值, 填到坑中
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 在左区间找到比基准值大的值, 填到右边的坑中
            arr[right] = arr[left];
        }
        // 最后把基准值填到剩下的坑中
        arr[left] = pivot;
        return left;
    }

    // 前后指针法
    private static void pointerQuick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = pointerPartition(arr, left, right);
        pointerQuick(arr, left, pivot - 1);
        pointerQuick(arr, pivot + 1, right);
    }

    private static int pointerPartition(int[] arr, int left, int right) {
        // prev 负责钉在比基准小的值上, prev+1 位置的值就是比基准值大的数据
        int prev = left;
        // cur 负责找比基准值小的数据, "撵" 到前面
        int cur = left + 1;
        while (cur <= right) {
            // arr[cur] <= arr[left] 表示: cur的位置就是比基准值小的元素的位置
            // arr[++prev] != arr[cur] 如果prev下一个元素的位置不是cur所在的位置, 则说明
            // prev+1 位置元素应该与 cur 位置元素相交换, 保证基准值前面的数都比它小,后面的数都比它大
            if (arr[cur] <= arr[left] && arr[++prev] != arr[cur]) {
                swap(cur, prev, arr);
            }
            cur++;
        }
        swap(left, prev, arr);
        return prev;
    }


    // 快排非递归
    private static void quickSortByStack(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        Stack<Integer> stack = new Stack<>();
        int pivot = partition(arr, start, end);
        // 当前序列左边还有两个或两个以上的元素, 才能压入栈中, 作为下一个区间的左右边界
        if (pivot - 1 > start) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        // 同理, 当前序列右区间还有两个或两个以上的元素, 才压入栈中
        if (pivot + 1 < end) {
            stack.push(pivot + 1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
            // 如果不为空, 拿出子区间的左右边界
            end = stack.pop();
            start = stack.pop();
            pivot = partition(arr, start, end);
            if (pivot - 1 > start) {
                stack.push(start);
                stack.push(pivot - 1);
            }
            if (pivot + 1 < end) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }



    // 归并排序
    public static void mergeSort(int[] arr) {
        mergeSortFun(arr, 0, arr.length - 1);
    }

    private static void mergeSortFun(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSortFun(arr, left, mid);
        mergeSortFun(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int left1 = left;
        int right1 = mid;
        int left2 = mid + 1;
        int right2 = right;

        int[] tmp = new int[right - left + 1];
        int i = 0;
        while (left1 <= right1 && left2 <= right2) {
            if (arr[left1] <= arr[left2]) {
                tmp[i] = arr[left1++];
            } else {
                tmp[i] = arr[left2++];
            }
            i++;
        }

        // 如果两个有序数组中存在多余的元素, 下面两个 while 就是为了防止这一情况
        while (left1 <= right1) {
            tmp[i++] = arr[left1++];
        }

        while (left2 <= right2) {
            tmp[i++] = arr[left2++];
        }

        // 把临时数组元素拷贝到原数组当中
        for (int j = 0; j < tmp.length; j++) {
            arr[j + left] = tmp[j];
        }
    }

    // 非递归实现归并
    public static void mergeSortByStack(int[] arr) {
        int gap = 1;
        int n = arr.length;
        // 如果整个数组长度为 8
        // 当 gap = 4 时, 就是将含4个元素的两个组进行合并
        // 合并之后就是有序的, 因此 gap >= n 时就不用再合并了
        while (gap < n) {
            for (int i = 0; i < n; i += 2 * gap) {
                int left = i;
                int mid = left + gap - 1; // mid可能会越界
                int right = mid + gap;

                if (mid >= n) {
                    mid = n - 1;
                }

                if (right >= n) {
                    right = n - 1;
                }
                merge(arr, left, mid, right);
            }
            gap *= 2;
        }
    }

    // 计数排序
    public static void countSort(int[] arr) {
        // 找到最大值和最小值, 构成count数组的容量
        int minVal = arr[0];
        int maxVal = arr[0];

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < minVal) {
                minVal = arr[i];
            }
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }

        int len = maxVal - minVal + 1;
        int[] count = new int[len];

        // 将原数组元素出现的次数统计在count中
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - minVal]++;
        }

        // 遍历count数组, 按从小到大的顺序把元素覆盖掉原数组
        int index = 0;
        for (int i = 0; i < len; i++) {
            while (count[i] != 0) {
                arr[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[10];
        // 对里面的元素随机赋值
        random(arr);
        System.out.println("原数组为: " + Arrays.toString(arr));
        countSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}
